1. Field of the Invention
The present invention relates to data compression systems which may be used, for example, to reduce the space required by data for storage in a mass storage device such as a hard disk, or to reduce the bandwidth required to transmit data.
2. Background Art
The invention is particularly concerned with data compression systems using dynamically compiled dictionaries. In such systems (see, for example, EP-A-0127815, Miller and Wegman) an input data stream is compared with strings stored in a dictionary. When characters from the data stream have been matched to a string in the dictionary the code for that string is read from the dictionary and transmitted in place of the original characters. At the same time when the input data stream is found to have character sequences not previously encountered and so not stored in the dictionary then the dictionary is updated by making a new entry and assigning a code to the newly encountered character sequence. This process is duplicated on the transmission and reception sides of the compression system. The dictionary entry is commonly made by storing a pointer to a previously encountered string together with the additional character of the newly encountered string.